package com.zdp.leetcodeMiddle;


import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
提示：

0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-k-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 最小k个数_17_14 {
    public static void main(String[] args) {
        最小k个数_17_14 demo = new 最小k个数_17_14();
        int[] arr = new int[] {
                1,3,5,7,2,4,6,8

        };
        int k = 4;
        demo.smallestK(arr,k);
    }

    /*
    * 解题思路： 利用快排思想  找中枢 确认小于的数
    * */
    public int[] smallestK(int[] arr, int k) {

        f(arr,k,0,arr.length-1);
        int[] result = new int[k];
        for(int i =0;i<k;i++){
            result[i] = arr[i];
        }
        return result;
    }

    private void f(int[] arr, int k, int left, int right){
       if(left <right){
           int point = getPoint(arr,left,right);
           int length = point - left +1;
           if(length == k){ //若当前找的中枢点前面正好有k个元素（含中枢点），那么这就是最小的k个数
               return ;
           }else if(length < k){ // 若只能确认 少于k个的元素，那么还需要确认其余的 k-length个元素
               f(arr,k-length,point+1,right);
           }else{ // 因为 中枢点前面的数 多于k个 ，所以无法确认 需要继续划分
               f(arr,k,left,point-1);
           }
       }
    }

    private int getPoint(int[] arr ,int left,int right){
        // 找中枢点
        int x = arr[right];
        int i =left-1;
        int j = left;
        for(;j<right;j++){
            if(arr[j] < x){
                swap(arr,++i,j);
            }
        }
        swap(arr,++i,right);
        return i;
    }


    private void swap(int[] arr,int A,int B){
        int temp = arr[A];
        arr[A] = arr[B];
        arr[B] = temp;
    }
}
